// 二分查找 https://blog.csdn.net/rxbook/article/details/130956745
package main

import "fmt"

// 二分查找:递归实现
func BinarySearch1(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	return BinarySearchRecursive(a, v, 0, n-1)
}
func BinarySearchRecursive(a []int, v int, low, high int) int {
	if low > high {
		return -1
	}
	mid := (low + high) / 2
	if a[mid] == v {
		return mid
	} else if a[mid] > v {
		return BinarySearchRecursive(a, v, low, mid-1)
	} else {
		return BinarySearchRecursive(a, v, mid+1, high)
	}
}

// 二分查找:循环实现
func BinarySearch2(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	low := 0
	high := n - 1
	for low <= high { //注意:循环退出条件low<=high，而不是low<high
		mid := (low + high) / 2
		if a[mid] == v {
			return mid
		} else if a[mid] > v {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// 二分查找: 查找第一个等值的元素
func BinarySearch3(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	low := 0
	high := n - 1
	for low <= high {
		mid := (low + high) / 2
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			//重点需要改造这里:当中间元素刚好等于被查找的元素时,需要确认这个元素是不是第一个出现
			//如果mid等于0,说明前面没有元素了,那这个元素肯定是第一个出现;
			//如果mid-1位置的元素已经不等于要查找的元素了,那么当前mid这个位置就是第一个.
			if mid == 0 || a[mid-1] != v {
				return mid
			} else {
				//如果当前元素的前一个元素也等于被查找的元素，说明当前元素不是第一个出现，
				//说明要查找的元素应该在[low,mid-1]区间，需要更新high = mid - 1
				high = mid - 1
			}
		}
	}
	return -1
}

// 二分查找:查找最后一个等值的元素
func BinarySearch4(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	low := 0
	high := n - 1
	for low <= high {
		mid := (low + high) / 2
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			if mid == n-1 || a[mid+1] != v {
				return mid
			} else {
				//相比 BinarySearch3,主要改动这里
				low = mid + 1
			}
		}
	}
	return -1
}

// 二分查找: 查找第一个大于指定值的元素
func BinarySearch5(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	low := 0
	high := n - 1
	for low <= high {
		mid := (high + low) / 2
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			//主要改动这里
			if mid != n-1 && a[mid+1] > v {
				return mid + 1
			} else {
				low = mid + 1
			}
		}
	}
	return -1
}

// 二分查找: 查找最后一个小于指定值的元素
func BinarySearch6(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	low := 0
	high := n - 1
	for low <= high {
		mid := (low + high) / 2
		if a[mid] > v {
			high = mid - 1
		} else if a[mid] < v {
			low = mid + 1
		} else {
			//主要改动这里
			if mid == 0 || a[mid-1] < v {
				return mid - 1
			} else {
				high = mid - 1
			}
		}
	}
	return -1
}

func main() {
	// 不存在重复元素的数组中使用二分查找
	arr := []int{1, 3, 5, 6, 8}
	fmt.Println(BinarySearch1(arr, 6)) // 3
	fmt.Println(BinarySearch2(arr, 6)) // 3

	// 存在重复元素的数组中查找第一个等于给定值的元素,可能出问题
	myArr := []int{1, 3, 4, 5, 6, 8, 8, 8, 11, 21}
	fmt.Println(BinarySearch1(myArr, 8)) //7
	fmt.Println(BinarySearch2(myArr, 8)) //7

	// 查找第一个出现8的元素的位置
	fmt.Println(BinarySearch3(myArr, 8)) //5
	// 查找最后一个出现8的元素的位置
	fmt.Println(BinarySearch4(myArr, 8)) //7
	// 查找第一个大于8的元素:11的位置
	fmt.Println(BinarySearch5(myArr, 8)) //8
	// 查找最后一个小于11的元素:最后一个8的位置
	fmt.Println(BinarySearch6(myArr, 11)) //7
}
